"""递归函数"""""

'''定义'''

# 递归函数在代码体中，会自己调用自己，需要设置终止条件,如果不设置就会陷入死循环
# 递归由两部分组成：递推和回溯
# 递推：一层一层的调用下去，每一次调用问题的规模会越来越小
# 回溯：当遇到终止条件时，会向上一层一层回溯，直到最初调用的结果


# def a(n):
#     if n > 0:
#         return a(n - 1)
#     elif n <= 0:
#         return 1


'''递归举例'''


def sum_num(n):  # 计算n以内之和的函数,n是正整数
    num = 1  # 设置初始值
    result = 0
    while num <= n:
        result += num
        num += 1
    return result


print(sum_num(5))


def sum_num_func(n):  # 使用递归实现上述列子
    if n == 1:
        return 1
    else:
        result = n + sum_num_func(n - 1)
        return result



def list_expand(lst, depth=0):
    # 缩进符号（每级递归增加2个空格，直观区分层级）
    indent = "  " * depth
    # 进入函数时打印当前调用信息
    print(f"{indent}┌── [递归深度 {depth}] 调用 list_expand，参数：{lst}")

    result_ls = []
    for i in lst:
        # 打印当前处理的元素
        print(f"{indent}│   处理元素：{i}")

        if not isinstance(i, list):
            # 非列表元素直接添加
            result_ls.append(i)
            print(f"{indent}│   → 元素非列表，添加到结果：{result_ls}")
        else:
            # 列表元素触发递归
            print(f"{indent}│   → 元素是列表，进入下一层递归处理")
            # 递归调用，深度+1
            sub_result = list_expand(i, depth + 1)
            # 递归返回后，打印子结果
            print(f"{indent}│   ← 递归返回子结果：{sub_result}")
            # 合并子结果到当前结果
            result_ls.extend(sub_result)
            print(f"{indent}│   → 合并子结果后：{result_ls}")

    # 函数结束时打印当前调用的返回结果
    print(f"{indent}└── [递归深度 {depth}] 返回结果：{result_ls}")
    return result_ls



ls = [1, 2, 3, 4, [5, 6, 7, [8, 9, ['a', 'b']]]]
print("\n最终展开结果：", list_expand(ls))

def list_expand(lst):
    result_ls = []
    for i in lst:
        if not isinstance(i,list):  # //判断不是列表,1不是列表返回F 与not和一起返回T
            result_ls.append(i)
        else:
            result_ls.extend(list_expand(i))  #自己调用自己 函数名后面带参数了能传参数
    return result_ls
ls = [1, 2, 3, 4, [5, 6, 7, [8, 9, ['a', 'b']]]]  # 全部拆开，必须保持元素之间顺序不变
print(list_expand(ls))

"""快速排序"""""


# 思想是使用分治法，将原始数组分为一个较大的数组和较小的数组，然后递归的排序这两个子数组
# 设置一个基准值，一般是取中间

# 升序排列
def quicksort(arr):
    print(f'当前排序的数组是：{arr}')
    if len(arr) <= 1:  # 递归的终止条件
        return arr
    else:
        pivot = arr[0]  # 初始化基准值
        right, middle, left = [], [], []  # 初始化较大较小两个子数组 和 基准值相等的子数组
        for i in arr:
            if i > pivot:
                right.append(i)
            elif i < pivot:
                left.append(i)
            else:
                middle.append(i)
        print(f'本次调用的基准值是{pivot}')
        print(f'本次调用子数组情况，较小的是：{left}，中间的是：{middle}，较大的是{right}')
        return quicksort(left) + middle + quicksort(right)


ls = [23, 34, 3, 1, 231, 25, 234, 12, 312, 3, 1, -123123423]
print(quicksort(ls))